/*
https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones/solution/bu-han-lian-xu-1de-fei-fu-zheng-shu-by-l-9l86/
 */

public class Solution600 {
    public int findIntegers(int n) {
        int t=n,l=0;
        while (t>0){
            t=t/2;
            l=l+1;
        }
        int[] f=new int[50];
        f[0]=f[1]=1;
        for (int i=2;i<=l;i++){
           f[i]=f[i-1]+f[i-2];
        }
        int ans=0,pre=0;
        for (int i=l;i>=0;i--){
            int v=1<<(i-1);
            if (n>=v) {
                n = n - v;
                ans = ans + f[i];
                if (pre == 1) {
                    break;
                }
                pre=1;
            }else{
                pre=0;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution600().findIntegers(8));
    }
}
